Continuing advances in technology combined with dropping production costs have led to a proliferation of electronic devices that incorporate or use advanced digital circuits including desktop computers, laptop computers, hand-held devices, such as Personal Digital Assistants (PDA), and hand-held computers, cellular telephones, printers, digital cameras, facsimile machines and other electronic devices. These digital circuits are typically required to provide the basic functionality of the electronic device. Digital circuits may also be incorporated in many other household or business appliances. To continue to develop and produce these digital circuits, fast, efficient means of synthesizing and/or designing these circuits are required. In addition, at each step of the design process, it is necessary to verify the correct operation of these digital circuits.
Digital circuit verification includes, (1) ensuring that the circuit performs the correct functionality and (2) ensuring that the circuit satisfies the timing requirements. Functional verification ensures that the circuit produces the correct result or output. Timing verification ensures that the correct output is produced within a given amount of time or that the output is available when it is required. One possible approach for timing verification is timing simulation where the functionality and delay of each component in the circuit is used to repeatedly simulate the circuit response for each input stimulus from a set of input stimuli. The disadvantage of timing simulation is that the verification cannot be guaranteed for the input stimuli that have not been simulated. An alternative approach to timing verification is timing analysis, which overcomes this disadvantage by analyzing (rather than simulating) the circuit for all stimuli that can possibly occur at the circuit-inputs. Furthermore, timing analysis can also be used to determine the maximum circuit delay, as opposed to simply ensuring that the circuit satisfies the given timing requirements.
Typically, a clock is used to coordinate the sequence of events performed by the digital circuit. This coordination is referred to as synchronization. The period of time between successive clock cycles is the clock period.
Analyzing the timing of a digital circuit includes an examination of the circuit path from the primary input or latching element, through one or more combinational circuit components to a primary output or latching element. A combinational circuit component is one whose output function depends solely on the input values applied to it, not on any past history or internal state. Latching elements include registers, d-type and similar type flip-flops or other storage devices that store the value present at its input upon the occurrence of a synchronization event, such as a clock edge. Timing analysis ensures that the delays along a circuit path from the input to the output are less than the period of time between the synchronization events, such as successive clock cycles.
The simplest form of timing analysis performs only topological analysis, i.e., it only accounts for the delay of each component and their interconnectivity (the way they are connected with each other) and ignores the functionality of the circuit components. One of the earliest timing analysis tools which followed this approach was Program Evaluation and Review Technique (PERT), which calculated the maximum delay of a circuit as the delay of the topologically longest path in the circuit. The run-time complexity of this analysis is “big O of M,” i.e., O(M), where M stands for the number of circuit components. In other words, the time it takes to perform this analysis is linearly proportional to the circuit size. Any timing analysis algorithm will have to look at each circuit component at least once during its analysis, therefore a run-time complexity that is linearly proportional to circuit size is optimal (and hence, desirable). PERT is described in T. I. Kirkpatrick and N. R. Clark, “PERT as an aid to logic design,” IBM Journal of Research and Development, vol. 10, 1966, pp. 135–141 which is hereby incorporated by reference in its entirety.
Unfortunately, there are two drawbacks with PERT: (1) it over-estimates the maximum circuit delay because it does not account for false paths, and (2) it cannot handle combinational loops that may be present in the circuit.
A path is said to be false or unsensitizable when a signal cannot propagate from the beginning to the end of the path under any combination of primary inputs. FIG. 1 illustrates a sensitization example.
Unit gate delays and zero wire delays are assumed in the following functional analysis of FIG. 1. Input 101 is connected to non-inverting buffer 102, output 104 of buffer 102 is connected to a first input of AND gate 105 and input 103 is connected to a second input of AND gate 105. Input 103 is also connected to buffer 106. Output 107 of AND gate 105 is connected to a first input of OR gate 109 and output 108 of buffer 106 is connected to a second input of OR gate 109. OR gate 109 has output 110.
The circuit path starting at input 101, through buffer 102, output 104, AND gate 105, output 107, OR gate 109 and output 110 has a delay of three units (one unit delay for each of buffer 102, AND gate 105 and OR gate 109). For a rising or falling transition (at time zero) to propagate from input 101 through this circuit path to output 110, the second input (103) of AND gate 105 must be a logic 1 (non-controlling or sensitizing value) at the time the transition propagates through AND gate 105 (i.e., at time t=1 unit). In order for this to occur, input 103 should be a logic 1 at time t=1 unit. Similarly, the second input (108) to OR gate 109 must be at logic 0 (non-controlling or sensitizing value) at the time the transition along the path propagates through OR gate 109 (i.e., at time t=2 units). In order for this to occur, the output of buffer 106 should be a logic 0 at time t=2 units, which implies that input 103 should be a logic 0 at time t=1 unit. It is seen that to meet these two criteria, input 103 is required to be both a logic 1 and a logic 0 at time=1 unit which is not possible. Therefore, a transition cannot propagate through this circuit path. This path is therefore not sensitizable. The maximum delay of this circuit path is therefore less than three units, but PERT will evaluate the circuit delay as three units since the topologically longest path in the circuit is equal to three units.
Several algorithms have been proposed in the literature to perform timing analysis accounting for false paths. An example of such an algorithm is S. Devadas, K. Keutzer, and S. Malik, “Computation of floating mode delay in combinational logic circuits: Theory and algorithms,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, December 1993, pp. 1913–1922. These algorithms are able to determine the maximum circuit delay with greater accuracy, however, they have super-linear run-time complexity (i.e., their run-time scales worse than linearly with respect to circuit size), so they are less efficient than purely topological timing analysis (i.e., PERT). Moreover, they still cannot handle combinational loops that may be present in the circuit.
A loop in a circuit occurs when a combinational path goes through the same combinational component more than once. Combinational components include AND gates, OR gates, etc., but excludes latches and registers. A loop is said to be combinational when, in spite of the structural feedback, there is no logical feedback that is transmitted to the primary outputs. In other words, a signal cannot go completely around a combinational loop and then propagate to a primary output (it will be stopped either before it completes one entire loop, or before it reaches the primary output).
Several techniques have been proposed in the literature to perform timing analysis accounting for combinational cycles. One example is found in S. Malik, “Analysis of cyclic combinational circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 7, July 1994, pp. 950–956, the disclosure of which is incorporated by reference herein. Malik has proposed a technique for estimating the maximum delay of any given cyclic combinational circuit by unrolling the cyclic circuit to obtain an equivalent acyclic circuit. This potentially makes the circuit large and complex. This technique relies on Binary Decision Diagrams (BDDs) for the necessary logical analysis. These factors make the technique impractical for large circuits. Another example is found in A. Srinivasan and S. Malik, “Practical analysis of combinational circuits,” Proceedings Custom Integrated Circuits Conference, 1996, pp. 381–384, the disclosure of which is incorporated by reference herein. Srinivasan and Malik have proposed a heuristic process for handling a restricted case of cyclic combinational circuits. This is based on finding a minimal set of gates that, when removed, results in an acyclic circuit. The heuristic process is super-linear in run-time complexity, therefore the authors proposed a user-specified budget to terminate the heuristic unsuccessfully if it exceeds the budget.
In summary, timing analysis that does not account for false paths and combinational loops, although being of linear run-time complexity, over-estimates the maximum delay of a circuit. Algorithms that include false paths and combinational loops analysis are super-linear in run-time complexity and, therefore, less efficient.